package com.sjb.training.lc;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: 有点儿意思
 * @Description:
 */
public class TwoQuickSort {

    private static Random random = new Random();

    public static void main(String[] args) {
        int[] nums = {3, 6, 8, 10, 1, 2, 1};
        quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    static void quickSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        // 哨兵划分操作
        int pivotIndex = partition(nums, l, r);
        // 递归左（右）子数组进行哨兵划分
        quickSort(nums, l, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, r);
    }

    static int partition(int[] nums, int l, int r) {
        // 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
        int pivotIndex = l + random.nextInt(r - l + 1);
        swap(nums, pivotIndex, l);

        int i = l + 1;
        int j = r;

        while (i <= j) {
            while (i <= j && nums[i] <= nums[l]) {
                i++;
            }
            while (i <= j && nums[j] > nums[l]) {
                j--;
            }
            if (i < j) {
                swap(nums, i, j);
            }
        }
        swap(nums, l, j); // 将基准数放到正确的位置
        return j;
    }

    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
